| class H_SET{E} < $SET{E} |
|---|
| **** | Implementation of sets using dynamic hash tables. This implementation is also available of dealing with equal but not same objects. |
| $SET{_} | $RO_SET{_} | $STR | $CONTAINER{_} | $ELT{_} | $ELT | DYNAMIC_BUCKET_TABLE{_,_} | COMPARE{_} | SET_INCL{_} | RO_SET_INCL{_} |
| SET{_} |
| as_array: ARRAY{E} .. Included as as_array |
|---|
| clear |
|---|
| **** | Extremely inefficient. Must be rewritten by someone who has looked at the implementation (delete(elt!) may have problems) Creates a separate list of elements to delete to separte out iteration from modification |
| map_copy: SAME .. Included as copy |
|---|
| **** | Returns a copy of self with all properties set like self. |
| copy_from(a: $ELT{E}) .. Included as copy_from |
|---|
| **** | Clear old elts and insert the elements of self |
| create(e: $ELT{E}): SAME |
|---|
| create: SAME .. Included as create |
|---|
| create_from(a: ARRAY{E}): SAME |
|---|
| create_from(e: $ELT{E}): SAME .. Included as create_from |
|---|
| delete(e: E) |
|---|
| delete(e:E): E |
|---|
| **** | Removes an element from the set. Returns the deleted element. Returns void (or E::nil if E inherits $NIL{E}) if there is no element to delete. |
| diff(s: $RO_SET{E}): SAME |
|---|
| diff_view(s: $RO_SET{E}): $RO_SET{E} .. Included as diff_view |
|---|
| **** | See the comment for "union_view" |
| equals(a:$RO_SET{E}): BOOL .. Included as equals |
|---|
| **** | Returns 'true' if every element of self is elt_eq to an element in 'a' and vice versa. Neither may be void. |
| get(e:E): E |
|---|
| **** | Returns the element equal to 'e' from the set. Returns void or E::nil if there is no such element. Self may not be void. |
| has(e:E): BOOL |
|---|
| insert(e:E) |
|---|
| insert_replace(e:E) |
|---|
| **** | Inserts e into the set. If there is already an element equal to e in the set, the old element will be replaced. |
| insert_replace(e:E): E |
|---|
| **** | Does the same like insert_replace but returns the old element which is being replaced or the same object if there was no old one. |
| intersection(s:$RO_SET{E}): SAME |
|---|
| intersection_view(s: $RO_SET{E}): $RO_SET{E} .. Included as intersection_view |
|---|
| **** | See the note for "union_view" |
| is_empty: BOOL .. Included as is_empty |
|---|
| **** | Do not do size=0. Finding size may require iteration through all elements - quite wasteful for just "is_empty" |
| is_subset_of(s: $RO_SET{E}): BOOL .. Included as is_subset_of |
|---|
| **** | Return true if "self" is a subset of "s" |
| size: INT |
|---|
| str: STR .. Included as str |
|---|
| **** | Prints out a string version of the array of the components that are under $STR |
| sym_diff(s: $RO_SET{E}): SAME |
|---|
| sym_diff_view(s: $RO_SET{E}): $RO_SET{E} .. Included as sym_diff_view |
|---|
| **** | See the comment for "union_view" |
| to_diff(a: $ELT{E}) .. Included as to_diff |
|---|
| to_intersection(a: $ELT{E}) .. Included as to_intersection |
|---|
| to_sym_diff(a: $ELT{E}) .. Included as to_sym_diff |
|---|
| to_union(a: $ELT{E}) .. Included as to_union |
|---|
| union(s: $RO_SET{E}): SAME |
|---|
| union_view(s: $RO_SET{E}): $RO_SET{E} .. Included as union_view |
|---|
| **** | Return a read-only "view" of the union of "self" and "s" The resulting view just points to the two component sets and computes its elements on-the-fly, as needed. As a result, this form of union requires almost no additional space but may it may take slightly longer to perform operations |
| elt!: E |
|---|
| attr asize: INT; .. Included as asize |
|---|
| **** | The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal. |
| attr asize: INT; .. Included as asize |
|---|
| **** | The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal. |
| attr bound: INT; .. Included as bound |
|---|
| **** | Upper bound for split_pos. Is always initial_size * 2.pow(doubles) |
| attr bound: INT; .. Included as bound |
|---|
| **** | Upper bound for split_pos. Is always initial_size * 2.pow(doubles) |
| bucket(i:INT): BUCKET .. Included as bucket |
|---|
| create_from_internal(s: $RO_SET{E}): SET{E} .. Included as create_from_internal |
|---|
| **** | Used as an auxilliary routine by the view creation routines. When the return type can be any $RO_SET, then by default a "SET" will be constructed and used |
| create_sized(initial_size:INT): SAME .. Included as create_sized |
|---|
| **** | Creating a table with another minimal size. This might be useful to avoid shrinking of large table which might get very empty. |
| dbg: STR .. Included as dbg |
|---|
| **** | Returns an interal string representation of the hashtable. For debugging only. |
| attr doubles: INT; .. Included as doubles |
|---|
| **** | Number of times the initial table size has been doubled. |
| attr doubles: INT; .. Included as doubles |
|---|
| **** | Number of times the initial table size has been doubled. |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_eq(e1,e2:ETP):BOOL .. Included as elt_key_eq |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_hash(e:ETP):INT .. Included as elt_key_hash |
|---|
| **** | A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_key_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt |
|---|
| **** | The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants. |
| elt_nil: ETP .. Included as elt_nil |
|---|
| **** | Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void
_ |
| get_set_of_self: SAME .. Included as get_set_of_self |
|---|
| grow .. Included as grow |
|---|
| **** | Increases the size of the array by one. The functions changing the size of the bucket table: They are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow) |
| hash(e:E): INT .. Included as hash |
|---|
| **** | Returns the bucket to store e. This number will be generated from the hash-value and be normailzed through the actual size of the set. |
| is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil |
|---|
| shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio |
|---|
| shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio |
|---|
| attr minsize: INT; .. Included as minsize |
|---|
| **** | Lower bound for the store size. |
| attr minsize: INT; .. Included as minsize |
|---|
| **** | Lower bound for the store size. |
| attr n_inds: INT; .. Included as n_inds |
|---|
| **** | Returns the number of elements (resp. indices) in the table. |
| attr n_inds: INT; .. Included as n_inds |
|---|
| **** | Returns the number of elements (resp. indices) in the table. |
| set_bucket(i:INT,l:BUCKET) .. Included as set_bucket |
|---|
| shrink .. Included as shrink |
|---|
| **** | Decreases the size of the array by one. Resizes the storage area, if neccessary. |
| attr split_pos: INT; .. Included as split_pos |
|---|
| **** | Position of the next bucket to split. |
| attr split_pos: INT; .. Included as split_pos |
|---|
| **** | Position of the next bucket to split. |
| attr store: AREF{BUCKET}; .. Included as store |
|---|
| **** | Here is the data being stored. |
| attr store: AREF{BUCKET}; .. Included as store |
|---|
| **** | Here is the data being stored. |
| update_delete .. Included as update_delete |
|---|
| **** | Checks the actual fill ratio of the set. Removes a bucket from the hash table if the ratio is low enough. |
| update_insert .. Included as update_insert |
|---|
| **** | Checks the actual fill ratio of the set. Adds a bucket to the hash table if the ratio is high enough. The functions changing the size of the bucket table are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow) |
| shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio |
|---|
| **** | For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.) |
| shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio |
|---|
| **** | For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.) |